<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4781：[Usaco2017 Open]Paired Up</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2017 Open]Paired Up</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2017 Open]Paired Up</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2017 Open]Paired Up                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>Farmer John finds that his cows are each easier to milk when they have another cow nearby for moral&nbsp;</div>
<div>support. He therefore wants to take his Mcows (M&le;1,000,000,000, M even) and partition them into M/2</div>
<div>&nbsp;pairs. Each pair of cows will then be ushered off to a separate stall in the barn for milking. The&nbsp;</div>
<div>milking in each of these M/2 stalls will take place simultaneously.To make matters a bit complicated</div>
<div>, each of Farmer John's cows has a different milk output. If cows of milk outputs Aand B are paired&nbsp;</div>
<div>up, then it takes a total of A+Bunits of time to milk them both.Please help Farmer John determine th</div>
<div>e minimum possible amount of time the entire milking process will take to complete, assuming he pair</div>
<div>s the cows up in the best possible way.</div>
<div></div>
<div>
<div>John有n种牛(n&lt;=100000)每种牛有数量x与时间y牛的总数为m要将m头牛分为m/2对，每对的时间花费为两牛时间之</div>
<div>和问最大的那对的最小值m&lt;=1e9 y&lt;=1e9</div>
</div>
<div></div>
<p></p></p><hr/><h3>输入格式</h3><p><div>The first line of input contains N(1&le;N&le;100,000). Each of the next N lines contains two integers x&nbsp;</div>
<div>and y, indicating that FJ has x cows each with milk output y (1&le;y&le;1,000,000,000). The sum of the x</div>
<div>'s is M, the total number of cows.</div>
<div></div>
<p></p></p><hr/><h3>输出格式</h3><p><div>Print out the minimum amount of time it takes FJ's cows to be milked, assuming they are optimally&nbsp;</div>
<div>paired up.</div>
<div></div>
<p></p></p><hr/><h3>样例输入</h3><pre>3
1 8
2 5
1 2</pre><hr/><h3>样例输出</h3><pre>10
Here, if the cows with outputs 8+2 are paired up, and those with outputs 5+5 are paired up, the both
 stalls take 10 units of time for milking. Since milking takes place simultaneously, the entire proc
ess would therefore complete after 10 units of time. Any other pairing would be sub-optimal, resulti
ng in a stall taking more than 10 units of time to milk.</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Silver</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4781" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4781" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>